//假设按照升序排序的数组在预先未知的某个点上进行了旋转。 
//
// ( 例如，数组 [0,1,2,4,5,6,7] 可能变为 [4,5,6,7,0,1,2] )。 
//
// 搜索一个给定的目标值，如果数组中存在这个目标值，则返回它的索引，否则返回 -1 。 
//
// 你可以假设数组中不存在重复的元素。 
//
// 你的算法时间复杂度必须是 O(log n) 级别。 
//
// 示例 1: 
//
// 输入: nums = [4,5,6,7,0,1,2], target = 0
//输出: 4
// 
//
// 示例 2: 
//
// 输入: nums = [4,5,6,7,0,1,2], target = 3
//输出: -1 
// Related Topics 数组 二分查找 
// 👍 829 👎 0

package leetcode.editor.cn;
//Java：搜索旋转排序数组
public class P33SearchInRotatedSortedArray{
    public static void main(String[] args) {
        Solution solution = new P33SearchInRotatedSortedArray().new Solution();
        // TO TEST
        int nums[]={3,1};
        int target=1;
        System.out.println(solution.search(nums,target));
    }
    //leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int search(int[] nums, int target) {
        if(nums==null||nums.length<=0){
            return -1;
        }
        int len=nums.length;
        int begin=0;
        int end=len-1;
        return searchTarget(nums,begin,end,target);
    }

    /*
    使用递归来求解这道题目
    * */
    public  int searchTarget(int[] nums,int begin,int end,int target){
        if(begin>end){
            return -1;
        }
        int mid=begin+((end-begin)>>>1);
        if(nums[mid]==target){
            return mid;
        }
        if(nums[begin]<=nums[mid]){//左半部分有序  注意这里如果没有这个等号会出错，这个边界条件需要注意
            if(target<nums[mid]&&target>=nums[begin]){//数据位于有序的那一部分
               return searchTarget(nums,begin,mid-1,target);
            }else{
               return searchTarget(nums,mid+1,end,target);
            }

        }else{//右半部分有序
            if(target>nums[mid]&&target<=nums[end]){//数据位于有序的那一部分
                return searchTarget(nums,mid+1,end,target);
            }else{
                return searchTarget(nums,begin,mid-1,target);
            }
        }
    }
}
//leetcode submit region end(Prohibit modification and deletion)

}
